#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int QueueDataType;

typedef struct QueueNode
{
    QueueDataType data;
    struct QueueNode* next;
}QueueNode;

typedef struct Queue
{
    QueueNode* Head;
    QueueNode* Ptail;
    int size;
}Queue;

void InitQueue(Queue* ps)
{
    assert(ps);

    ps->Head = NULL;
    ps->Ptail = NULL;
    ps->size = 0;
}

void QueueDestroy(Queue* ps)
{
    assert(ps);

    QueueNode* cur = ps->Head;
    while (cur != NULL)
    {
        QueueNode* Next = cur->next;
        free(cur);
        cur = Next;
    }
    ps->Head = ps->Ptail = NULL;
    ps->size = 0;
}

bool QueueEmpty(Queue* ps)
{
    assert(ps);

    return ps->size == 0;
}

int QueueSize(Queue* ps)
{
    assert(ps);

    return ps->size;
}

void QueuePush(Queue* ps, QueueDataType x)
{
    assert(ps);

    QueueNode* NewNode = (QueueNode*)malloc(sizeof(QueueNode));
    if (NewNode == NULL)
    {
        perror("QueueNode()");
        exit(1);
    }
    NewNode->data = x;
    NewNode->next = NULL;
    if (ps->Ptail == NULL)
    {
        ps->Head = ps->Ptail = NewNode;
    }
    else
    {
        ps->Ptail->next = NewNode;
        ps->Ptail = ps->Ptail->next;
    }
    ps->size++;
}

void QueuePop(Queue* ps)
{
    assert(ps);
    assert(!QueueEmpty(ps));

    if (ps->Head->next == NULL)
    {
        free(ps->Head);
        ps->Head = ps->Ptail = NULL;
        ps->size = 0;
    }
    else
    {
        QueueNode* Next = ps->Head->next;
        free(ps->Head);
        ps->Head = Next;
        ps->size--;
    }
}

QueueDataType QueueTop(Queue* ps)
{
    assert(ps);
    assert(!QueueEmpty(ps));

    return ps->Head->data;
}

QueueDataType QueueBack(Queue* ps)
{
    assert(ps);
    assert(!QueueEmpty(ps));

    return ps->Ptail->data;
}

typedef struct
{
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate()
{
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
    if (obj == NULL)
    {
        perror("myStackCreate()");
        exit(1);
    }
    InitQueue(&obj->q1);
    InitQueue(&obj->q2);
    return obj;
}

void myStackPush(MyStack* obj, int x)
{
    assert(obj != NULL);

    if (!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1, x);
    }
    else
    {
        QueuePush(&obj->q2, x);
    }
}

int myStackPop(MyStack* obj)
{
    assert(obj != NULL);

    Queue* EmptyQ = &obj->q1;
    Queue* nonEmptyQ = &obj->q2;
    if (QueueEmpty(&obj->q1) != true)
    {
        EmptyQ = &obj->q2;
        nonEmptyQ = &obj->q1;
    }
    while (QueueSize(nonEmptyQ) > 1)
    {
        QueuePush(EmptyQ, QueueTop(nonEmptyQ));
        QueuePop(nonEmptyQ);
    }

    QueueDataType Top = QueueTop(nonEmptyQ);
    QueuePop(nonEmptyQ);
    return Top;
}

int myStackTop(MyStack* obj)
{
    if (!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

bool myStackEmpty(MyStack* obj)
{
    assert(obj);

    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj)
{
    assert(obj != NULL);

    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}
